package algorithms.leaning.class03;

import common.util.MyUtil;

/**
 * 求数组arr[L..R]中的最大值，怎么用递归方法实现。
 * <p>
 * 1）将[L..R]范围分成左右两半。左：[L..Mid]  右[Mid+1..R]
 * 2）左部分求最大值，右部分求最大值
 * 3） [L..R]范围上的最大值，是max{左部分最大值，右部分最大值}
 * <p>
 * 注意：2）是个递归过程，当范围上只有一个数，就可以不用再递归了
 *
 * @author guichang
 * @date 2021/5/30
 */

@SuppressWarnings("all")
public class Code8_递归_最大值 {

    public static void main(String[] args) {
        int[] nums = MyUtil.createRandomArray(10, -2, 20);
        MyUtil.print(max(nums, 0, nums.length - 1));
    }

    public static int max(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = left + ((right - left) >> 1);
        int maxLeft = max(nums, left, mid);
        int maxRight = max(nums, mid + 1, right);
        return Math.max(maxLeft, maxRight);
    }

}